Module# 14: Sorting Techniques Lecture#54: Programs for Sorting
Part-II
// Example 54.1: Programming for Radix sort
/* This program
defines a generic class to store a collection. */
class GenericArraySorting<T extends Comparable<T>> {
T a[];
GenericArraySorting(T x[]) { // Define a constructor
a = x;
}
T getData(int i) { // To return the element stored in the i-th
place
return a[i];
}
void printData() { // A method to print
the elements in array a
for(int i = 0; i < a.length; i ++)
System.out.print(this.getData(i) + " "); // Print the i-th
element
System.out.println();
/* This program sorts an array of data using
Insertion sort technique. */
T division(T x, int y) {
if (x == null || y == 0)
return null;
if (x instanceof Integer)
return (T)new Integer(x.intValue() / y);
if (x instanceof Short)
return (T)new Integer(x.shortValue() / y);
if (x instanceof Byte)
return (T)new Integer(x.byteValue() / y);
if (x instanceof Long)
return (T)new Long(x.longValue() / y);
else
throw new
IllegalArgumentException("Type " + x.getClass() + " is not
supported.");
}
}
/* This program find a constituent element.
*/
T modulus(T x, int y) {
if (x == null || y == 0)
return null;
if (x instanceof Integer)
return (T)new Integer(x.intValue() % y);
if (x instanceof Short)
return (T)new Integer(x.shortValue() % y);
if (x instanceof Byte)
return (T)new Integer(x.byteValue() % y);
if (x instanceof Long)
return (T)new Long(x.longValue() % y);
else
throw new IllegalArgumentException("Type " + x.getClass() + " is not
supported.”);
}
/* This program find a constituent element.
*/
T getMax(){
T max=a[0];
for(int i=1;i<a.length-1;i++) {
if(a[i].compareTo(max)==1)
max=a[i];
}
return max;
}
private static <T> T[] copyArray(T[] source) {
return source.clone();
}
/* This program find a constituent element.
*/
void countSort(int exp) {
int i,size=a.length,count[]=new int[10];
T[] output=copyArray(a);
for(i=0;i<size;i++)
count[modulus(division(a[i],exp),10).intValue()]++;
for(i=1;i<10;i++)
count[i]+=count[i-1];
for(i=size-1;i>=0;i--) {
output[count[modulus(division(a[i],exp),10).intValue()]-1]=a[i];
count[modulus(division(a[i],exp),10).intValue()]--;
}
for(i=0;i<size;i++)
a[i]=output[i];
}
/* This program find a constituent element.
*/
void radixSort(){
int exp=1;
T max=this.getMax();
Long m=new Long(division(max,exp).longValue());
for(;m>0;exp=exp*10){
this.countSort(exp);
m=division(max,exp).longValue();
}
}
} // End of the generic
class definition
/* This program find a constituent element.
*/
public class TestRadixSort{
public static void main(String[] args) {
Integer i[ ] = {59, 44, 79, 74, 88};
// Store the data into generic array
GenericArraySorting<Integer> arrayInt = new GenericArraySorting<Integer>(i);
// Printing the data….
System.out.print("Array Before Sorting : ");
arrayInt.printData();
arrayInt.radixSort();
System.out.print("Sorted Array is : ");
arrayInt.printData();
System.out.println();
}
}
// Example 54.2:
Programming for Quick sort
/* This program defines generic class and
many utility methods in it. */
class GenericArraySorting<T extends Comparable<T>> {
T a[];
GenericArraySorting(T x[]) { // Define a constructor
a = x;
}
T getData(int i) { // To return the element stored in the i-th
place
return a[i];
}
void printData() { // A generic method
to print the elements in array a
for(int i = 0; i < a.length; i ++)
System.out.print(this.getData(i) + " "); // Print the i-th element in a
System.out.println(); // Print a new line
}
/* This method for partition is defined
below. */
int partition(T arr[], int low, int high) {
T pivot = arr[high];
int i = (low-1); // index of the left most element
T temp;
for (int j=low; j<high; j++) {
if (arr[j].compareTo(pivot)<0) {
i++;
temp = arr[i]; // swap arr[i] and arr[j]
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* This method define quick sort recursively.
*/
void quickSort(int low, int high){
if (low < high) {
/* pi is partitioning index */
int pi = partition(a, low, high);
// Recursively sort elements in the two
partitioned lists
quickSort(low, pi-1);
quickSort(pi+1, high);
}
}
} //End of the generic class definition
/* This method apply quick sort. */
public class TestQuickSort {
public static void main(String[] args) {
Integer i[ ] = {59, 44, 79, 74, 88};
// Store the data into generic array
GenericArraySorting<Integer> arrayIntObj = new GenericArraySorting<Integer>(i);
// Printing the data….
System.out.print("Array Before Sorting : ");
arrayIntObj.printData();
arrayIntObj.quickSort(0,i.length-1);
System.out.print("Sorted Array is : ");
arrayIntObj.printData();
System.out.println();
/* This method apply
quick sort to string data. */
String
st[ ] = {"deepak","debasis","data","subhra","zeeshan"};
// Store the data into generic array
GenericArraySorting<String> arrayString = new GenericArraySorting<String>(st);
// Printing the data….
System.out.print("Array Before Sorting : ");
arrayString.printData();
arrayString.quickSort(0,i.length-1);
System.out.print("Sorted Array is : ");
arrayString.printData();
}
}